package 所有可达路径;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: AirMan
 * @date: 2025/5/28 15:51
 * @description:
 */
public class Solution1 {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {

        path.add(0);    // 始终从0开始，所以总是需要把节点0加入
        dfs(graph, 0, graph.length - 1);
        return result;
    }


    private List<List<Integer>> result = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();

    public void dfs(int[][] graph, int start, int end) {
        if (start == end) {
            result.add(new ArrayList<>(path));
            return;
        }
        // 遍历当前节点所有关联的节点
        for (int i : graph[start]) {
            // 将当前节点保存在本次搜索路径中
            path.add(i);
            dfs(graph, i, end);
            path.remove(path.size() - 1);
        }
    }
}
